package com.cat.graphTheory;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/escape-a-large-maze/
 * @create 2025/9/23 11:11
 * @since JDK17
 */

public class Solution24 {
    static int N = ((int) 1e6), MAX;
    long BASE = 131L;
    Set<Long> set = new HashSet<>();
    int[] d = new int[] { -1, 0, 1, 0, -1 };

    public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
        for (var p : blocked) {
            set.add(p[0] * BASE + p[1]);
        }
        int n = blocked.length;
        MAX = (n - 1) * n / 2;
        return check(s, t) && check(t, s);
    }

    boolean check(int[] s, int[] t) {
        Set<Long> vis = new HashSet<>();
        Deque<int[]> q = new ArrayDeque<>();
        q.add(s);
        vis.add(s[0] * BASE + s[1]);
        while (!q.isEmpty() && vis.size() <= MAX) {
            var p = q.pollFirst();
            if (p[0] == t[0] && p[1] == t[1]) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + d[i], ny = p[1] + d[i + 1];
                if (nx == -1 || nx == N || ny == -1 || ny == N) {   // 越界
                    continue;
                }
                long pos = nx * BASE + ny;
                if (set.contains(pos) || vis.contains(pos)) {
                    continue;
                }
                q.add(new int[]{nx, ny});
                vis.add(pos);
            }
        }

        return vis.size() > MAX;
    }
}
